package org.lql.algo.codecrush.hot100.dynamicProgramming;

import java.util.Stack;

/**
 * @author: liangqinglong
 * @date: 2025-09-14 09:06
 * @description: 32. 最长有效括号 <a href="https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class LongestValidParentheses {


	public int longestValidParentheses(String s) {
		int ans = 0;
		Stack<Integer> stack = new Stack<>();
		stack.push(-1);
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				stack.push(i);
			} else {
				stack.pop();
				// 如果栈为空，说明当前右括号没有匹配的左括号，将当前右括号的索引入栈
				if (stack.isEmpty()) {
					stack.push(i);
				} else {
					// 如果栈不为空，计算当前有效子串的长度，并更新最长有效括号长度
					ans = Math.max(ans, i - stack.peek());
				}
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		LongestValidParentheses longestValidParentheses = new LongestValidParentheses();
		int i = longestValidParentheses.longestValidParentheses("(()");
		System.out.println(i);
		i = longestValidParentheses.longestValidParentheses(")()())");
		System.out.println(i);
	}
}
